#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int nthUglyNumber(int n);

int main()
{
	return 0;
}

int nthUglyNumber(int n)
{
	int* aux = calloc(n, sizeof(int));
	aux[0] = 1;
	int p2 = 0, p3 = 0, p5 = 0,
		num2 = 2, num3 = 3, num5 = 5;
	for (int i = 1; i < n; i++) {
		if (num2 < num3 && num2 < num5) {
			aux[i] = num2;
			num2 = aux[++p2] * 2;
		} else if (num3 < num5) {
			if (num2 != num3) aux[i] = num3;
			else i--;
			num3 = aux[++p3] * 3;
		} else {
			if (num5 != num2 && num5 != num3) aux[i] = num5;
			else i--;
			num5 = aux[++p5] * 5;
		}
		printf("%d\t",aux[i]);
	}

	return aux[n - 1];
}
